#include <bits/stdc++.h>
using namespace std;

#define MAXN 1000
#define LG2MAXN 32
struct tree_t
{
   int top, to[MAXN], pr[MAXN], la[MAXN];
   int de[MAXN], fa[MAXN], si[MAXN];
   int anc[MAXN][LG2MAXN + 1];
   tree_t()
   {
      memset(to, 0, sizeof(to));
      memset(pr, 0, sizeof(pr));
      memset(la, 0, sizeof(la));
      memset(si, 0, sizeof(si));
      memset(de, 0, sizeof(de));
      memset(fa, 0, sizeof(fa));
      memset(anc, 0, sizeof(anc));
      top = 0;
   }
   void link(int p, int c)
   {
      to[++top] = c;
      pr[top] = la[p];
      la[p] = top;
   }
   void bfs(int x)
   {
      for (int i = la[x]; i; i = pr[i])
      {
         bfs(to[i]);
      }
   }
   void bfs(int x, int fath)
   {
      for (int i = la[x]; i; i = pr[i])
      {
         if (to[i] != fath)
         {
            bfs(to[i], x);
         }
      }
   }

   void CalcAux(int x, int fath)
   {
      fa[x] = fath;
      de[x] = de[fath] + 1;
      si[x] = 1;
      anc[x][0] = fath;
      for (int j = 1; j < LG2MAXN; j++)
         anc[x][j] = anc[anc[x][j - 1]][j - 1];
      for (int i = la[x]; i; i = pr[i])
      {
         if (to[i] != fath)
         {
            CalcAux(to[i], x);
            si[x] += si[to[i]];
         }
      }
   }

   int LCA_a1(int x, int y)
   {
      while (x != y)
      {
         if (de[x] > de[y])
            x = fa[x];
         else
            y = fa[y];
      }
      return x;
   }

   int LCA_MoT(int x, int y)
   {
      if (de[x] < de[y])
         swap(x, y);
      int delta = de[x] - de[y];
      for (int j = 0; j < LG2MAXN; j++)
         if ((1 << j) & delta)
            x = anc[x][j];

      if (x == y)
         return x;
      for (int j = LG2MAXN; j >= 0; j--)
         if (anc[x][j] != anc[y][j])
            x = anc[x][j], y = anc[y][j];
      return anc[x][0];
   }

   void view(int n)
   {
      printf("%3s%5s%5s%5s%5s%5s%5s\n", "i", "fa", "de", "si", "da", "pr", "la");

      for (int i = 0; i < n; i++)
      {
         printf("%3d%5d%5d%5d%5d%5d%5d\n", i, fa[i], de[i], si[i], to[i], pr[i], la[i]);
      }
   }
};

int main()
{
   tree_t tr;
   // tree_t tr2;
   int x, y, n = 0;
   while (cin >> x >> y)
   {
      n = max(n, x);
      n = max(n, y);
      tr.link(x, y);
      tr.link(y, x);
      // tr2.link(x, y);
      // tr2.link(y, x);
   }
   tr.CalcAux(1, 0);
   tr.view(2 * n);
   // tr2.CalcAux(1, 0);
   // tr2.view(2 * n);
   x = 3, y = 11;
   printf("LCA(%d, %d)=%d (MoT:%d)\n", x, y, tr.LCA_a1(x, y), tr.LCA_MoT(x, y));
   x = 10, y = 11;
   printf("LCA(%d, %d)=%d (MoT:%d)\n", x, y, tr.LCA_a1(x, y), tr.LCA_MoT(x, y));
   x = 8, y = 11;
   printf("LCA(%d, %d)=%d (MoT:%d)\n", x, y, tr.LCA_a1(x, y), tr.LCA_MoT(x, y));
   return 0;
}